Solution: First Unique Character in a String
Let's solve the First Unique Character in a String problem using the Knowing What to Track pattern.
We'll cover the following
Statement#
For a given string of characters, s, your task is to find the first non-repeating character and return its index. Return if there’s no unique character in the given string.
Constraints:
- Only lowercase english letters are accepted.
- There are no spaces in the string.
Solution#
We need to keep track of the number of occurrences of each character in the string. To achieve this, we can use a hash map to store the character as a key and its number of occurrences in the string as its corresponding value.
The algorithm proceeds through the following steps:
-
Create a hash map and start a loop to traverse over the given input string.
-
At each iteration, we check if the current character is present in the hash map as a key.
-
If the key exists, we increment the value corresponding to this key character by .
-
Otherwise, add this new key-value pair in the hash map and set its value to .
-
-
Traverse over the input string to find the character in the hash map whose value equals .
- If it exists, return the index of this character in the string. Otherwise, return .
The slide deck below illustrates the key steps of the solution.
1 of 32
2 of 32
3 of 32
4 of 32
5 of 32
6 of 32
7 of 32
8 of 32
9 of 32
10 of 32
11 of 32
12 of 32
13 of 32
14 of 32
15 of 32
16 of 32
17 of 32
18 of 32
19 of 32
20 of 32
21 of 32
22 of 32
23 of 32
24 of 32
25 of 32
26 of 32
27 of 32
28 of 32
29 of 32
30 of 32
31 of 32
32 of 32
Let’s look at the code for this solution below:
Time complexity#
The cost of traversing the length of the input string twice is , which can be simplified to .
Space complexity#
The space complexity of the algorithm above is because, at any time, a total of keys will be stored in the hash map. This makes it a constant space used to store the frequency of the characters’ occurrence.
First Unique Character in a String
Find All Anagrams in a String